/**
 * 39. 组合总和
 * https://leetcode-cn.com/problems/combination-sum/
 */
const { displayNestedArray } = require('../../libs/public');

/**
 * @param {number[]} candidates
 * @param {number} length
 * @param {number} target
 * @return {number}
 */
function search(candidates, length, target) {
  let left = 0;
  let right = length - 1;
  while (left <= right) {
    const medium = Math.floor((left + right) / 2);
    if (candidates[medium] === target) {
      return medium;
    }
    if (candidates[medium] < target) {
      if (medium >= length - 1 || candidates[medium + 1] > target) {
        return medium;
      }
      left = medium + 1;
    } else {
      right = medium - 1;
    }
  }
  return -1;
}

/**
 * @param {number[]} candidates
 * @param {number} length
 * @param {number} target
 * @return {number[][]}
 */
function combinationSub(candidates, length, target) {
  const index = search(candidates, length, target);
  if (index < 0) {
    return null;
  }
  const candidate = candidates[index];
  const result = [];
  const currents = [];
  let rest = target;
  while (rest > 0) {
    const children = combinationSub(candidates, index, rest);
    if (children) {
      for (let i = 0; i < children.length; i += 1) {
        result.push([...children[i], ...currents]);
      }
    }
    rest -= candidate;
    currents.push(candidate);
  }
  if (!rest) {
    result.push(currents);
  }
  if (!result.length) {
    return null;
  }
  return result;
}

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b);
  const result = combinationSub(candidates, candidates.length, target);
  if (!result) {
    return [];
  }
  return result;
}

// console.log(displayNestedArray(combinationSum([2, 3, 6, 7], 7)) === '[[2,2,3],[7]]');
// console.log(displayNestedArray(combinationSum([2, 3, 5], 8)) === '[[2,2,2,2],[2,3,3],[3,5]]');
// console.log(displayNestedArray(combinationSum([2], 1)) === '[]');
// console.log(displayNestedArray(combinationSum([1, 2], 1)) === '[[1]]');
// console.log(displayNestedArray(combinationSum([1], 2)) === '[[1,1]]');
// console.log(displayNestedArray(combinationSum([2, 7, 6, 3, 5, 1], 9)) === '[[1,1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,2],[1,1,1,1,1,2,2],[1,1,1,2,2,2],[1,2,2,2,2],[1,1,1,1,1,1,3],[1,1,1,1,2,3],[1,1,2,2,3],[2,2,2,3],[1,1,1,3,3],[1,2,3,3],[3,3,3],[1,1,1,1,5],[1,1,2,5],[2,2,5],[1,3,5],[1,1,1,6],[1,2,6],[3,6],[1,1,7],[2,7]]');
console.log(displayNestedArray(combinationSum([3, 12, 9, 11, 6, 7, 8, 5, 4], 15)));
